The amount of data handled by information processing systems is increasing year by year, and accordingly storage systems with larger capacity are developed to back up the data growing in volume. Backup data often includes the same data as data that has already been stored in the storage system. Therefore, eliminating duplicate data inside backup data makes it possible to effectively utilize the storage resources of a storage system.
In order to check whether identical segments exist in a system, a conventional technique via which a three-stage search is performed to determine (1) whether a segment fingerprint is included in a memory buffer index; (2) whether a segment fingerprint is included in a Bloom filter fo an index; and (3) whether a segment fingerprint is included in an index, is well known (Patent Literature 1).